One of the ways that a computer application program is analyzed is for timing issues, such as to know how long a program will take to terminate regardless of its input and/or environment. For example, timing is used for responsiveness analysis, for performance analysis, (e.g., in estimating parameters such as throughput and scalability), and for identifying resource bottlenecks.
In sequential programs, computational complexity is sufficient for estimating the running time of some fragment of code, and the code's scalability. Other measures such as memory complexity or in general resource usage may be of interest when considering scalability, but using computational complexity to predict running time is generally sufficient for most analyses.
Techniques for computing sequential code complexity typically operate by having each loop instrumented with a counter variable; then the loop's complexity is determined by placing an upper bound on the counter, by using an abstract interpreter or an invariant generation tool. Recursive procedures are instrumented in the same manner. The analysis is compositional in that code fragments (procedures) are analyzed in isolation, then the results for each fragment are composed together.
However, concurrent programs cannot use such a simple method of timing analysis. Because each participating thread (or task, process, and so forth) performs local computations, exchanges data and synchronizes with other threads (by means of shared memory or message passing), computational complexity of the code executed by each thread is of little value. For example, the complexity results for concurrent code is not compositional, because depending on the number of CPUs and depending on whether two threads contend for/synchronize with the same resources, the total running time is a different function of the individual running times.